package org.laizili.solution.nowcodertop101.search;

/**
 * <a href="https://www.nowcoder.com/practice/fcf87540c4f347bcb4cf720b5b350c76?tpId=295&sfm=html&channel=nowcoder">BM19. 寻找峰值</a>
 * <p>
 * tags: 二分查找;
 */
public class BM19 {
    private static class Solution {
        /**
         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
         *
         * @param nums int整型一维数组
         * @return int整型
         */
        public int findPeakElement(int[] nums) {
            // write code here
            int len = nums.length;
            if (len == 1) {
                // 只有一个元素
                return 0;
            }
            int res = -1;
            for (int i = 0; res == -1 && i < len; i++) {
                int left = i - 1;
                int right = i + 1;
                if (left == -1) {
                    if (nums[i] > nums[right])
                        res = i;
                } else if (right == len) {
                    if (nums[i] > nums[left])
                        res = i;
                } else if ((nums[left] < nums[i] && nums[i] > nums[right]))
                    res = i;
            }
            return res;
        }
    }

    // 二分查找
    private static class Solution2 {
        /**
         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
         *
         * @param nums int整型一维数组
         * @return int整型
         */
        public int findPeakElement(int[] nums) {
            // write code here
            int left = 0, right = nums.length - 1;
            while (left < right) { // 区间至少有两个元素
                int mid = (left + right) / 2;
                if (nums[mid] < nums[mid + 1]) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            return left;
        }
    }
}
